/***************************************************************
*  Copyright (c) 2007 by GroupMe! Team (www.groupme.net)
*  All rights reserved.
*
*  This file is part of the GroupMe! Project. Source code of 
*  this project is closed and redistribution of this code is
*  prohibited. 
*  
*  Contact: http://www.groupme.net
*
*  This copyright notice MUST APPEAR in all copies of the file!
***************************************************************/
package net.groupme.search.strategy.metrics;

import java.util.ArrayList;
import java.util.List;

import net.groupme.search.strategy.model.AbstractWeightedIdentifiable;
import net.groupme.search.strategy.model.WeightedIdentifiableComparatorByWeight;

/**
 * created on 14 Jan 2008
 * 
 * This class provides some metrics (e.g. OSim, KSim) to compare two rankings with esach other. 
 * 
 * @author Fabian Abel, <a href="mailto:abel@l3s.de">abel@l3s.de</a>
 * @author last edited by: $Author: fabian $
 * 
 * @version $Revision: 1.8 $ $Date: 2009-03-11 23:15:05 $
 */
public class RankingMetrics {

	//TODO: mit TopK implementieren
	public static Double computeRecall(List<AbstractWeightedIdentifiable> relevantResources, List<AbstractWeightedIdentifiable> resources, int topK){
		Double recall = 0.0;
		for(AbstractWeightedIdentifiable resource: resources){
			if(relevantResources.contains(resource)){
				recall++;
			}
		}
		return recall/relevantResources.size();
	}
	//TODO: mit TopK implementieren
	public static double computePrecision(
			List<AbstractWeightedIdentifiable> relevantResources,
			List<AbstractWeightedIdentifiable> resources, int topK) {
		Double precision = 0.0;
		for(AbstractWeightedIdentifiable resource: resources){
			if(relevantResources.contains(resource)){
				precision++;
			}
		}
		return precision/resources.size();
	}
	/**
	 * Computes the OSim between two rankings:
	 * <pre>
	 * OSim = | intersectionOf(rankingA.sublist(0, topK), rankingB.sublist(0, topK) | / topK 
	 * </pre>
	 * @param rankingA a ranking where the best rated item is on the first position. (computed)
	 * @param rankingB a ranking where the best rated item is on the first position. (hand-selected)
	 * @param topK number of topK ranks to consider
	 * @return the OSim between both rankings
	 */
	public static final Double computeOSim(List<? extends AbstractWeightedIdentifiable> rankingA, List<? extends AbstractWeightedIdentifiable> rankingB, int topK){
		Double osim = new Double(0.0);
		if(rankingA.size() > topK){
			rankingA = rankingA.subList(0, topK);
		}
		if(rankingB.size() > topK){
			rankingB = rankingB.subList(0, topK);
		}

		if(rankingA.size() < topK && rankingA.size() < rankingB.size()){
			for(int i=0; i<rankingB.size() && i<topK; i++){
				if(rankingA.contains(rankingB.get(i))){
					osim += 1.0;
				}
			}
		}else{
			for(int i=0; i<rankingA.size() && i<topK; i++){
				if(rankingB.contains(rankingA.get(i))){
					osim += 1.0;
				}
			}
		}
		

		//usally we have to devide by topK - but if the length of rankingA is lesser than topK then we devide by the weighted middle of rankingA's and rankingB's length... 
		Double k = (rankingA.size() < topK ? ((new Integer(rankingA.size()).doubleValue() + new Integer(rankingB.size()).doubleValue()) / 2.0) : new Integer(topK).doubleValue());
		k = (rankingB.size() < topK ? ((new Integer(rankingA.size()).doubleValue() + new Integer(rankingB.size()).doubleValue()) / 2.0) : new Integer(topK).doubleValue());
		return osim / new Integer(topK).doubleValue();
	}
	
	public static final Double computeOSimTest(List<? extends AbstractWeightedIdentifiable> rankingA, List<? extends AbstractWeightedIdentifiable> rankingB, int topK){
		Double osim = new Double(0.0);
		for(int i=0; i<rankingA.size() && i<topK; i++){
			if(rankingB.contains(rankingA.get(i))){
				osim += 1.0;
			}
		}
		//usally we have to devide by topK - but if the length of rankingA is lesser than topK then we devide by the weighted middle of rankingA's and rankingB's length... 
		Double k = (rankingA.size() < topK ? ((new Integer(rankingA.size()).doubleValue() + new Integer(rankingA.size()).doubleValue()) / 2.0) : new Integer(topK).doubleValue());
		return osim / k;
	}
	
	/**
	 * Computes the KSim between two rankings:
	 * <pre>
	 * Let U be the union of rankingA and rankingB;
	 * rankingA' = rankingA.append(U - rankingA);
	 * rankingB' = rankingB.append(U - rankingB);
	 * 
	 * KSim = 
	 *   | (u, v) with u, v in U AND u != v AND  orderOf((u,v), rankingA) == orderOf((u,v), rankingB) |  
	 *      /  
	 *   (|U| * |U-1|) 
	 * </pre>
	 * The order is not determined by the occurrence within the list but via {@link WeightedIdentifiableComparatorByWeight}. This 
	 * is done because two items can be on the same rank when they have the same weight...
	 *  
	 * @param rankingA a ranking where the best rated item is on the first position.
	 * @param rankingB a ranking where the best rated item is on the first position.
	 * @param topK number of topK ranks to consider
	 * @return the KSim between both rankings
	 */
	public static final Double computeKSim(List<? extends AbstractWeightedIdentifiable> rankingA, List<? extends AbstractWeightedIdentifiable> rankingB, int topK){
		Double ksim = new Double(0.0);
		List<AbstractWeightedIdentifiable> rankingA2 = new ArrayList<AbstractWeightedIdentifiable>(rankingA);
		List<AbstractWeightedIdentifiable> rankingB2 = new ArrayList<AbstractWeightedIdentifiable>(rankingB);
		if(topK < rankingA2.size()){
			rankingA2 = rankingA2.subList(0, topK);
		}
		if(topK < rankingB2.size()){
			rankingB2 = rankingB2.subList(0, topK);
		}
		if(rankingA2.size() == 0 || rankingB2.size() == 0){
			return 0.0;
		}
		Double minA = rankingA2.get(rankingA2.size() - 1).getWeight();
		Double minB = rankingB2.get(rankingB2.size() - 1).getWeight();
		
		//rankingA um items erweitern, die in topK von rankingB vorkommen und vice versa; union aus rankingA und rankingB berechnen:
		List<AbstractWeightedIdentifiable> inBAndNotInA = itemsThatAreInXButNotInY(rankingB2, rankingA2);
		List<AbstractWeightedIdentifiable> inAAndNotInB = itemsThatAreInXButNotInY(rankingA2, rankingB2);
		List<AbstractWeightedIdentifiable> union = new ArrayList<AbstractWeightedIdentifiable>(rankingA2); 
		AbstractWeightedIdentifiable toAdd = null;
		for(AbstractWeightedIdentifiable wi: inBAndNotInA){
			toAdd = wi.clone();
			toAdd.setWeight(minA - 0.000001);
			rankingA2.add(toAdd);
			union.add(toAdd);
		}
		for(AbstractWeightedIdentifiable wi: inAAndNotInB){
			toAdd = wi.clone();
			toAdd.setWeight(minB - 0.000001);
			rankingB2.add(toAdd);
		}
		//rankingA2.addAll(inBAndNotInA); -> Schmeisst eine ConcurrentModificationException...
		//rankingB2.addAll(inAAndNotInB);
		
		//iterate over each possible pair (u,v) with u, v in U AND u != v
		AbstractWeightedIdentifiable u = null;
		AbstractWeightedIdentifiable v = null;
		WeightedIdentifiableComparatorByWeight comparator = new WeightedIdentifiableComparatorByWeight();
		for(int i = 0; i< union.size(); i++){
			for(int j=0; j<union.size(); j++){//test mit  j=i
				u = union.get(i);
				v = union.get(j);
				if(!u.equals(v)){
					//wenn u und v nicht in der topK von rankingA enthalten sind, dann wird ueber die Ordnung keine Aussage gemacht, gleiches gilt fuer rankingB:
					if( ! (
							(inBAndNotInA.contains(u) && inBAndNotInA.contains(v)) 
							|| (inAAndNotInB.contains(u) && inAAndNotInB.contains(v)))){
						//same order according to WeightedIdentifiableComparatorByWeight?
						if(	comparator.compare(
									rankingA2.get(rankingA2.indexOf(u)), 
									rankingA2.get(rankingA2.indexOf(v))) 
							 == 
							comparator.compare(
								   rankingB2.get(rankingB2.indexOf(u)), 
								   rankingB2.get(rankingB2.indexOf(v)))){
							ksim += 1.0;
						}
					}
				}
			}
		}
		return (ksim / (union.size() * (union.size()-1)));
	}
	/**
	 * This method returns all items that are contained in ranking X but not in ranking Y.
	 * @param rankingX ranking X
	 * @param rankingY ranking Y 
	 * @return all items that are contained in ranking X but not in ranking Y.
	 */
	public static final List<AbstractWeightedIdentifiable> itemsThatAreInXButNotInY(List<AbstractWeightedIdentifiable> rankingX, List<AbstractWeightedIdentifiable> rankingY){
		List<AbstractWeightedIdentifiable> notContainedInY = new ArrayList<AbstractWeightedIdentifiable>();
		for (AbstractWeightedIdentifiable identifiable : rankingX) {
			if(!rankingY.contains(identifiable)){
				notContainedInY.add(identifiable);
			}
		}
		return notContainedInY;
	}
	
}
